#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1010;
const int INF = 1e9;

int n, m;
vector<pair<int, int> > adj[MAXN]; // 邻接表
int dist[MAXN]; // 存储从起点到每个节点的最短距离
bool visited[MAXN]; // 标记数组，表示节点是否已经被访问

void dijkstra(int start) {
    fill(dist, dist + n, INF);
    fill(visited, visited + n, false);
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; // 优先队列，默认是大顶堆
    pq.push({0, start}); // 将起点加入队列，距离为0
    dist[start] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;

        for (auto &edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v; // 将节点编号从1开始转换为从0开始
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // 因为是无向图，所以添加两条边
    }

    dijkstra(0); // 假设起点是0号节点

    cout << dist[n - 1] <<endl ;

    return 0;
}